This application is based on applications Nos. 11-92050 and 11-92094 filed in Japan, the contents of which are incorporated herein by reference.
1. Technical Field of the Invention
The present invention relates to an image processing technique for recognizing a specific pattern included in an image.
2. Related Art
Conventionally, in an image processing apparatus, the position of a specific pattern included in an image has been detected and a pattern matching processing has been carried out to recognize the shape of the specific pattern by storing data on each pixel fetched into a camera or the like as binary data or multivalued data in an image memory and matching, for each pixel, the stored data with data on each pixel of a reference pattern stored beforehand in the memory. In this matching, the whole image has been scanned while shifting the reference pattern every pixel for an image including the specific pattern in the x or y direction of the image.
In this method, however, the image including the specific pattern and the reference pattern are shifted and matched every pixel. Therefore, there has been a problem in that a very long time is required for the process.
In the image recognizing process, moreover, examples of a method for detecting the position of the specific pattern of an image implementing a high speed include a method for creating a reduced image from the image, performing a pattern matching on the reduced image to retrieve the specific pattern, and carrying out retrieval in the region of an original image corresponding to the detecting position of the specific pattern on the reduced image again. In this method, however, the specific pattern cannot be detected accurately depending on an algorithm for creating the reduced image in some cases. For example, in the case of the image having a pixel value which is alternately different for each pixel such as checkers, when thinning is carried out every other pixel to create a reduced image, the reduced image thus created has only one of pixel values appearing on an original image. Consequently, a correct specific pattern cannot be detected from such a reduced image.
Moreover, examples of a process to be carried out prior to a process such as image recognition include a labeling process of detecting a region to be formed by pixels having the same value which are continuous in a binary image (hereinafter referred to as a xe2x80x9cconnecting regionxe2x80x9d) and giving a label number to the connecting region. As a method for the labeling process, various methods have conventionally been proposed.
FIG. 21 is a diagram illustrating one example of the labeling processes in the connecting region of the image according to the prior art. In FIG. 21, an original image 20 includes three connecting regions A, B and C. These connecting regions A, B and C are continuous regions comprising pixels having pixel value of xe2x80x9c1xe2x80x9d. When labeling the connecting region of the image, the whole image is scanned to examine the pixel value of each pixel and to give a provisional label number for a pixel decided to constitute the connecting region. At this time, the provisional label number is not always accurate. Therefore, re-labeling of the label number is carried out later in some cases. For this reason, information for the re-labeling is stored in tables 51 and 53. Then, an image is scanned again to replace the provisional label number with a real label number with reference to the tables 51 and 53.
More specifically, when a pixel having a pixel value of xe2x80x9c1xe2x80x9d is detected during the scanning of the image 20 in a first scanning operation, it is decided whether or not there are any adjacent pixels having a label number given thereto. If there is an adjacent pixel having a label given thereto, the same label number as in the adjacent pixel is given to the detected pixel. When a plurality of adjacent pixels have the label numbers given thereto, the same label number as in the adjacent pixel having a higher priority is given based on a predetermined priority. When there is no adjacent pixel having the label number given thereto, a new label number is given to the detected pixel. Thus, the inside of the image is scanned to give the label number of the pixel having the pixel number of xe2x80x9c1xe2x80x9d.
As described above, in the image having the label number given thereto, pixels having the same label number given thereto form one connecting region. However, a plurality of label numbers are given to one connecting region depending on the shape of the connecting region in some cases. As shown in FIG. 21, for example, a connecting region A of the image 20 is labeled as three regions having label numbers 2, 3 and 4 in an image 20xe2x80x2 as a result of the above-mentioned labeling. In the labeling process, a link table 51 is created. The link table 51 stores information indicating that three regions having the label numbers 2, 3 and 4 are identical. Furthermore, label editing is carried out to create a conversion table 53 for setting the label numbers 2, 3 and 4 to 2 and re-labeling the label numbers 3 and 4 thus generating a vacancy into a region having label numbers 5 and 6.
Then, in a second scanning operation, each of the pixels of the image 20xe2x80x2 is scanned and a label number is converted (re-labeled) into a real label number by referring to the information of the conversion table 53. Consequently, each region is finally labeled correctly as in an image 20xe2x80x3.
In the above-mentioned method, however, it is necessary to scan the whole image twice. Therefore, a long time is taken to perform the labeling process. The time required for the processing is prolonged as the size of the image is increased.
The present invention is directed to solve the above-mentioned problem, and has an object to provide an image processing apparatus and method capable of retrieving a specific pattern from an image at a high speed and a recording medium storing a program therefor.
The invention has another object to provide an image processing apparatus and method for a labeling processing in the connecting region of an image at a high speed, and a recording medium storing a program therefor.
In a first aspect of the invention, an image processing apparatus is provided for retrieving a specific pattern of an image. The apparatus comprises a unit for dividing the image into a plurality of block regions, each of the block regions having a predetermined size, a unit for creating a map image comprising a plurality of pixels, each of the pixels corresponding to one of the block regions by one to one, a unit for extracting features of the image for each of the block regions, a unit for deciding whether or not the extracted feature meets a predetermined condition, a unit for labeling the pixel on the map image based on a result of the decision, the pixel corresponding to the block region of which feature meets the condition, a unit for detecting a predetermined pattern for specifying a search region on the image from the labeled map image, a unit for specifying the search region based on a position on the map image in which the predetermined pattern is detected, and a unit for retrieving the specific pattern in the specified search region on the image.
In the apparatus, at least one of a concentration value of a pixel, an edge amount and a co-occurrence characteristic may be extracted as the feature amount. In the apparatus, the predetermined pattern for determining the search region may be detected by using a filter having the same size as a size of the specific pattern in the map image.
In a second aspect of the invention, an image processing method is provided for retrieving a specific pattern of an image. The method comprises dividing the image into a plurality of block regions, each of the block regions having a predetermined size, creating a map image comprising a plurality of pixels, each of the pixels corresponding to one of the block regions by one to one, extracting features of the image for each of the block regions, deciding whether or not the extracted feature meets a predetermined condition, labeling the pixel on the map image based on a result of the decision, the pixel corresponding to the block region of which feature meets the condition, detecting a predetermined pattern for specifying a search region on the image from the labeled map image, specifying the search region based on a position on the map image in which the predetermined pattern is detected, and retrieving the specific pattern in the specified search region on the image.
In a third aspect of the invention, a computer readable recording medium storing a program for controlling the computer to retrieve a specific pattern from an image is provided. The program is capable of executing the following functions: a function for dividing the image into a plurality of block regions, each of the block regions having a predetermined size; a function for creating a map image comprising a plurality of pixels, each of the pixels corresponding to one of the block regions by one to one; a function for extracting features of the image for each of the block regions; a function for deciding whether or not the extracted feature meets a predetermined condition; a function for labeling the pixel on the map image based on a result of the decision, the pixel corresponding to the block region of which feature meets the condition; a function for detecting a predetermined pattern for specifying a search region on the image from the labeled map image; a function for specifying the search region based on a position on the map image in which the predetermined pattern is detected; and a function for retrieving the specific pattern in the specified search region on the image.
In a fourth aspect of the invention, an image processing apparatus is provided for labeling a connecting region of an image. The apparatus comprises a flag memory including flags indicating whether or not each pixel of the image is finished with examination, a candidate stack for storing indexes, each of indexes specifying a pixel of which adjacent pixels are to be examined, a region memory for storing indexes, each of indexes indicating one of pixels constituting the connecting region, a labeling unit for labeling pixels specified by the indexes stored in the region memory, and a connecting region detecting unit for detecting the pixels constituting the connecting region. The connecting region detecting unit scans the image, examines whether or not a pixel of the image constitutes the connecting region, sets the flag for the examined pixel. When the pixel constituting the connecting region is first detected in the examination, the connecting region detecting unit (1) pushes an index of the detected pixel into the candidate stack, and stores the index to the region memory, 2) while there is at least one index stored in the candidate stack, repeats a) popping an index from the candidate stack to examine whether or not pixels adjacent to a pixel which is indicated by the popped index and of which flag indicates unexamined constitute the connecting region, b) when the adjacent pixels constitute the connecting region, pushing the indexes of the adjacent pixels into the candidate stack and storing the indexes to the region memory, and c) setting the flags for the adjacent pixels.
In the apparatus, the labeling unit may calculate a size of a region including pixels indicated by indexes stored in the memory when labeling pixels, and prohibit labeling the pixel when the calculated size is out of a predetermined range. In the apparatus, the region memory may comprise a stack memory.
In a fifth aspect of the invention, an image processing method is provided for labeling a connecting region of an image. The method comprises scanning the image, examining whether or not a pixel of the image constitutes the connecting region, setting the flag for the examined pixel, and when the pixel constituting the connecting region is first detected in the examination, (1) pushing an index of the detected pixel into a stack, and storing the index to a memory, (2) while there is at least one index stored in the stack, repeating a) popping an index from the stack to examine whether or not pixels adjacent to a pixel which is indicated by the popped index and of which flag indicates unexamined constitute the connecting region, b) when the adjacent pixels constitute the connecting region, pushing the indexes of the adjacent pixels into the stack and storing the indexes to the memory, and c) setting the flags for the adjacent pixels, (3) reading all indexes out from the memory when there is no index stored in the stack to label pixels indicated by the read indexes with same number.
In a sixth aspect of the invention, a computer readable recording medium in which a program for controlling the computer to label a connecting region of an image is provided. The program is capable of executing the following functions: a function for scanning the image; a function for examining whether or not a pixel of the image constitutes the connecting region; a function for setting the flag for the examined pixel; and when the pixel constituting the connecting region is first detected in the examination, (1) a function for pushing an index of the detected pixel into a stack, and storing the index to a memory, (2) while there is at least one index stored in the stack, repeating a) a function for popping an index from the stack to examine whether or not pixels adjacent to a pixel which is indicated by the popped index and of which flag indicates unexamined constitute the connecting region, b) when the adjacent pixels constitute the connecting region, a function for pushing the indexes of the adjacent pixels into the stack and storing the indexes to the memory, and c) a function for setting the flags for the adjacent pixels, (3) a function for reading all indexes out from the memory when there is no index stored in the stack to label pixels indicated by the read indexes with same number.